// 利用异或运算的特性：a ^ a = 0 和 a ^ 0 = a
// 先找到所有数字（包括完整序列和实际数组）的异或结果，这个结果其实是两个缺失数字的异或
// 根据异或结果找到两个缺失数字的不同位，以此为依据将数字分组。每组分别进行异或运算，最终得到两个缺失数字
class Solution {
    public int[] missingTwo(int[] nums) {
        // 先把所有数都异或在一起
        int tmp = 0;
        for (int x : nums) tmp ^= x;
        for (int i = 1; i <= nums.length+2 ; i++) {
            tmp ^= i;
        }

        // 找出a，b两个比特位不同的那一位（一定会跳出循环）
        int diff = 0;
        while (true) {
            if (((tmp >> diff) & 1) == 1) break;
            else diff++;
        }

        int[] ret = new int[2];
        for (int x : nums) {
            if ((x >> diff & 1) == 1) {
                ret[1] ^= x;
            } else {
                ret[0] ^= x;
            }
        }

        // 将所有的数按照diff位不同，分为两类来异或
        for (int i = 1; i <= nums.length+2 ; i++) {
            if ((i >> diff & 1) == 1) {
                ret[1] ^= i;
            } else {
                ret[0] ^= i;
            }
        }
        return ret;
    }
}